package com.algorithm7;

import java.util.Arrays;

public class QuickSort2 {
    private static void quickSort(int[] array,int low,int height){
        if(low<height){
            int pivot = partion(array,low,height);
            quickSort(array,low,pivot-1);
            quickSort(array,pivot+1,height);
        }

    }

    private static int partion(int[] array,int p,int q){
        int piv = q;
        int i = p;
        int j = q;
        while(i<j){
            while(i<j && array[i]<array[piv]){
                i++;
            }
            while(i<j && array[j]>array[piv]){
                j--;
            }
            //if(array[i]>array[j]){
                swap(array,i,j);
            //}
        }
        swap(array,i,piv);
        return i;
    }

    private static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void main(String[] args){
        int[] array = {10,5,6,3,4,8,7,1,2};
        //int[] array = new int[]{4,3,5,8,9,7,10,6,1,2};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));

    }
}
